#include <iostream>
#include <stdio.h>
#include <cstddef>
#include <functional>
using namespace std;


内存分配与释放

向system heap申请空间
考虑多线程状态
考虑内存不足的应变措施
考虑过多小型区块可能造成内存碎片问题 SGI设计了双层级分配器。

C++内存分配::operator new() 释放内存 ::operator delete()
这两个全局函数相当于是
C malloc和 free函数
SGI正是以malloc和free完成内存的分配与释放。


两级分配器：
第一级分配器
  直接使用malloc和free
  allocate()
  deallocate()
  模拟C++ set_new_handler()处理内存不足情况。
第二级分配器
   当分配区块超过128BYTES ，视为足够大，调用第一分配器
   当区块小于128bytes时,视为过小,为了降低额外负担。采用复杂的memory pool整理方式。
   不再使用第一级分配器.
1、维护16个自由的链表结构free list 
负责16种小型区块的次配置能力
内存池mempry pool以malloc()配置而得。
如果内存不足，调用一级配置器。有处理程序。
2、如果需求块大于128 BYTES 转而调用一级空间配置器。

无论alloc被定义为第一级或者第二级分配器,SGI为他再封装一个接口。使得分配器
的接口能够符合STL规格。




// STL版本
// HP STL 
// 所有实现STL版本的始祖
//   唯一需要遵守的是：必须在所有文件中加上HP的版本生命和运用权限声明。
//   属于open source范畴。
// P.J 实现版本
//   继承自HP版本。每一个头文件都有HP的版本说明
//   此外还加上P.J 的个人版权声明
//   备VISUAL C++ 采用
//   可读性较低
//   属于open source 范畴
// RW 实现版本
//   继承自HP版本。每一个头文件都有HP的版本说明
//   此外还加上Rouge WAVE 公司版权声明
//   属于 open source范畴
//   备C++ builder采用 
//   可读性不错。
// STLPort 实现版本
//   以SGI STL为蓝本的高度可移植性实现版本。

// SGI STL实现版本
//    继承自HP版本，所以每一个头文件上面都有HP的版本说明
//    此外还加上SGI的公司版权声明
//    属于open source 范畴
//    被GCC采用。
//    可读性很高。
//    为了具有高度移植性，考虑了不同编译器的不同编译能力。

// SGI标准的空间分配器std::allocator 
// 效率不佳。只把C++的：：operator new和 ::operator delete做了一层
// 浅浅的封装。

// SGI特殊的空间分配器 std::alloc
// STL 标准规定分配器定义于 <memory> 中。

// stl_construct.h构造函数与析构函数 
// stl_alloc.h 一级二级空间配置器 alloc 彼此合作。
// std_uninitialized.h fill或者copy大块数据内存。
// 与对象设置初值有关。最差调用construct.
// 最佳情况调用memmove直接进行移动。

// 真正在SGI STL中大显身手的分配器或为一级分配器,或为二级分配器。

// 对象构造与析构
// STL规定分配器必须拥有名为construct()和destory()的两个成员函数，然而SGI特殊的空间分配器
// std::alloc并未遵循这一规则。所以实际上这部分属于STL allocator。但不属于std::alloc

// construct () 泛化 T1*p const T2&value --------> new (p) T1(value)

// destory()  泛化

// __destory()
// ForwardIterator,FordwardIterator

// 特化 char*,char*  no-op trivial destructor 特化 
//        for(;first<last;...) destory(&*first) __false_type 
//     特化 no-op  __true_type
// 特化 wchar_t* wchar_t*
// 特化 T* pointer pointer-> ~T()


// //根据STL的规范 以下是STL的必要接口
// allocator::value_type
// allocator::pointer
// allocator::const_pointer
// allocator::reference
// allocator::const_reference
// allocator::size_type
// allocator::difference_type;

// allocator::rebind  //??
// allocator::allocator(){}
// allocator::allocator(const allocator&){}
// template <class U> allocator::allocator(const allocator<U> &){}
// allocator::~allocator(){}

// //&x
// pointer allocator:::address(reference x) const
// const_pointer allocator::address(const_reference x) const

// pointer allocator::allocate(size_type n, const void * = 0)

// void allocator::deallocate(pointer p,size_type n)

// size_type allocator::max_size() const

// //new((void *)p) T(x)
// void allocator::construct(pointer p,const T&x)

// void allocator::destory(pointer p)

// .....
// //空间分配器
// class Foo{ ...};
// Foo *fp = new Foo;
// delete fp;

// new内含 :: operator new分配内存,调用构造函数构造对象。
// delete :内含调用析构函数析构对象,调用::operator delete释放内存。

// STL allocator将new 和delete的2阶操作进行了分离。

// 内存分配:: alloc::allocate()分配内存负责
// 内存释放:: alloca::deallocate()负责
// 对象构造：： alloc::construct()负责
// 对象析构：： alloca::destory()负责
//容器 container  
//分配器 allocator
//算法 algorithms
//迭代器 iterators
//适配器 adaptors 
//仿函数 functors

////////////////////////////////////////////////////////////////
/*
#define __STL_TEMPLATE_NULL

namespace xmspace
{
    //main template
    template <class Key>
    struct hash
    {
        //
        void operator()()
        {
            cout << " hash <T> " << endl;
        }
    };
    //template spacilization
    // explicit specilization
    template <>
    struct hash<char>
    {
        void operator()()
        {
            cout << " hash <char> " << endl;
        }
    };

    template <>
    struct hash<unsigned char>
    {
        void operator()()
        {
            cout << " hash <unsigned cha> " << endl;
        }
    };

    template <>
    struct hash<unsigned long>
    {
        void operator()()
        {
            cout << " hash <unsigned long> " << endl;
        }
    };
} // end of xmnamsapace
 */
///////////////////////////////////////////////////////////////////////
// void testconfigofcompiler(void);
// void teststaticmemberintemplate();
// void testPairiclass();
// void testdefaulttemplates();
// void testnotypetamplate();
// void teststlnulltempargs();
// void testspacialization();
/*
void testconfigofcompiler(void)
{
    cout<<"This is a test for STL configuration macros."<<endl;
    cout<<"It will print out the macros defined by the compiler."<<endl;
    cout<<"If you see this message, it means the test is running."<<endl<<endl;
#ifdef _PTHREADS
    cout<<" DEFINE__STL_PTHREADS"<<endl;
#endif

# if defined(__sgi) && !defined(__GNUC__)
#   if !defined(_BOOL)
        cout<<"__STL_NEED_BOOL"<<endl;
#   endif
#   if !defined(_TYPENAME_IS_KEYWORD)
        cout<<"__STL_NEED_TYPENAME"<<endl;
#   endif
#   ifdef _PARTIAL_SPECIALIZATION_OF_CLASS_TEMPLATES
        cout<<"__STL_CLASS_PARTIAL_SPECIALIZATION"<<endl;
#   endif
#   ifdef _MEMBER_TEMPLATES
        cout<<"__STL_MEMBER_TEMPLATES"<<endl
#   endif
#   if !defined(_EXPLICIT_IS_KEYWORD)
        cout<<"__STL_NEED_EXPLICIT"<<endl;
#   endif
#   ifdef __EXCEPTIONS
        cout<<"__STL_USE_EXCEPTIONS"<<endl;
#   endif
#   if (_COMPILER_VERSION >= 721) && defined(_NAMESPACES)
        cout<<"__STL_USE_NAMESPACES"<<endl;
#   endif
#   if !defined(_NOTHREADS) && !defined(__STL_PTHREADS)
        cout<<"__STL_SGI_THREADS"<<endl
#   endif
# endif

# ifdef __GNUC__
    cout <<"__GNUC__ is begin........."<<endl;
//#   include <_G_config.h>
#   if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
                cout <<"__STL_STATIC_TEMPLATE_MEMBER_BUG"<<endl;
                cout<<"__STL_NEED_TYPENAME"<<endl;
                cout<<"__STL_NEED_EXPLICIT"<<endl;
#   else
                cout<<"__STL_CLASS_PARTIAL_SPECIALIZATION"<<endl;
                cout<<"__STL_FUNCTION_TMPL_PARTIAL_ORDER"<<endl;
                cout<<"__STL_EXPLICIT_FUNCTION_TMPL_ARGS"<<endl;
                cout<<"__STL_MEMBER_TEMPLATES"<<endl;
#   endif

#   if !defined(_NOTHREADS) && __GLIBC__ >= 2 && defined(_G_USING_THUNKS)
        cout<<"__STL_PTHREADS"<<endl
#   endif
#   ifdef __EXCEPTIONS
        cout <<"__STL_USE_EXCEPTIONS"<<endl;
#   endif
# endif

# if defined(__SUNPRO_CC)
    cout<<"__STL_NEED_BOOL"<<endl;
    cout<<"__STL_NEED_TYPENAME"<<endl
    cout<<"__STL_NEED_EXPLICIT"<<endl;
    cout<<"__STL_USE_EXCEPTIONS"<<endl;
# endif

# if defined(__COMO__)
        cout<<"__STL_MEMBER_TEMPLATES"<<endl
        cout<<"__STL_CLASS_PARTIAL_SPECIALIZATION"<<endl;
        cout<<"__STL_USE_EXCEPTIONS"<<endl;
        cout<<"__STL_USE_NAMESPACES"<<endl;
# endif

# if defined(_MSC_VER)
    cout<<"_MSC_VER is begin........."<<endl;
#   if _MSC_VER > 1000
// #     include <yvals.h>
        cout <<"include yvals.h"<<endl;
#   else
        cout<<"__STL_NEED_BOOL"<<endl;
#   endif
    cout<<" __STL_NO_DRAND48"<<endl;
    cout<<" __STL_NEED_TYPENAME"<<endl;
#   if _MSC_VER < 1100
        cout<<"__STL_NEED_EXPLICIT"<<endl;
#   endif
    cout<<" __STL_NON_TYPE_TMPL_PARAM_BUG"<<endl;
    cout<<" __SGI_STL_NO_ARROW_OPERATOR"<<endl;
#   ifdef _CPPUNWIND
        cout<<" __STL_USE_EXCEPTIONS"<<endl;
#   endif
#   ifdef _MT
        cout<<" __STL_WIN32THREADS"<<endl;
#   endif
    cout<<"_MSC_VER is end........."<<endl;
# endif

# if defined(__BORLANDC__)
    cout<<"__BORLANDC__ is begin........."<<endl;
    cout<<" __STL_NO_DRAND48"<<endl;
    cout<<" __STL_NEED_TYPENAME"<<endl;
    cout<<" __STL_LIMITED_DEFAULT_TEMPLATES"<<endl;
    cout<<" __SGI_STL_NO_ARROW_OPERATOR"<<endl;
    cout<<" __STL_NON_TYPE_TMPL_PARAM_BUG"<<endl;
#   ifdef _CPPUNWIND
    cout<<" __STL_USE_EXCEPTIONS"<<endl;
#   endif
#   ifdef __MT__
        cout<<"__STL_WIN32THREADS"<<endl;
#   endif
    cout<<"__BORLANDC__ is end........."<<endl;
# endif


# if defined(__STL_NEED_BOOL)
    cout<<"__STL_NEED_BOOL is begin........."<<endl;
    cout<<"typedef int bool"<<endl;
    cout<<"define true 1"<<endl;
    cout<<"define false 0"<<endl;
    cout<<"__STL_NEED_BOOL is end........."<<endl;
# endif

# ifdef __STL_NEED_TYPENAME
    cout<<"define typename"<<endl;
# endif

# ifdef __STL_NEED_EXPLICIT
    cout<<"define explicit"<<endl;
# endif
cout<<endl;
cout<<endl;
# ifdef __STL_EXPLICIT_FUNCTION_TMPL_ARGS
    cout<<" __STL_NULL_TMPL_ARGS <> is begin"<<endl;
# else
    cout<<"__STL_NULL_TMPL_ARGS"<<endl;
    cout<<"__STL_NULL_TMPL_ARGS is ending....."<<endl;
# endif
cout<<endl;
cout<<endl;
# ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    cout<<"define __STL_TEMPLATE_NULL template<>"<<endl;
# else
    cout<<"define __STL_TEMPLATE_NULL"<<endl;
    cout<<"__STL_TEMPLATE_NULL is ending............"<<endl;
# endif
cout<<endl;
cout<<endl;
// __STL_NO_NAMESPACES is a hook so that users can disable namespaces
// without having to edit library headers.
# if defined(__STL_USE_NAMESPACES) && !defined(__STL_NO_NAMESPACES)
    cout<<"__STL_USE_NAMESPACES begin......."<<endl;
    cout<<" __STD std"<<endl;
    cout<<" __STL_BEGIN_NAMESPACE namespace std {"<<endl;
    cout<<" __STL_END_NAMESPACE }"<<endl;
    cout<<"  __STL_USE_NAMESPACE_FOR_RELOPS"<<endl;
    cout<<" __STL_BEGIN_RELOPS_NAMESPACE namespace std {"<<endl;
    cout<<" __STL_END_RELOPS_NAMESPACE }"<<endl;
    cout<<"   define __STD_RELOPS std"<<endl;
    cout<<"__STL_USE_NAMESPACES end........."<<endl<<endl;
# else
    cout<<"! __STL_USE_NAMESPACES begin......."<<endl;
    cout<<"__STD"<<endl;
    cout<<" __STL_BEGIN_NAMESPACE "<<endl;
    cout<<" __STL_END_NAMESPACE "<<endl;
    cout<<"undef  __STL_USE_NAMESPACE_FOR_RELOPS"<<endl;
    cout<<" __STL_BEGIN_RELOPS_NAMESPACE "<<endl;
    cout<<" __STL_END_RELOPS_NAMESPACE "<<endl;
    cout<<" __STD_RELOPS "<<endl;
    cout<<"! __STL_USE_NAMESPACES end........."<<endl<<endl;
# endif
cout<<endl;
cout<<endl;
# ifdef __STL_USE_EXCEPTIONS
    cout<<"__STL_USE_EXCEPTIONS is begin .............."<<endl;
    cout<<"__STL_TRY try"<<endl;
    cout<<"__STL_CATCH_ALL catch(...)"<<endl;
    cout<<"__STL_RETHROW throw"<<endl;
    cout<<" __STL_NOTHROW throw()"<<endl;
    cout<<" __STL_UNWIND(action) catch(...) { action; throw; }"<<endl;
    cout<<"__STL_USE_EXCEPTIONS is end..............."<<endl;
# else
    cout<<"!__STL_USE_EXCEPTIONS is begining.............."<<endl;
    cout<<" __STL_TRY "<<endl;
    cout<<" __STL_CATCH_ALL if (false)"<<endl;
    cout<<" __STL_RETHROW "<<endl;
    cout<<" __STL_NOTHROW "<<endl;
    cout<<" __STL_UNWIND(action) "<<endl;
    cout<<"!__STL_USE_EXCEPTIONS is ending.............."<<endl;

# endif
cout<<endl;
cout<<endl;
#ifdef __STL_ASSERTIONS
    cout<<"!__STL_ASSERTIONS is begining.............."<<endl;
    cout<<"# include <stdio.h>"<<endl;
    cout<<"   __stl_assert(expr)  if (!(expr)) { fprintf(stderr, "%s:%d STL assertion failure: %s\n", \
              __FILE__, __LINE__, # expr); abort(); }"<<endl;
#else
    cout<<" __stl_assert(expr)"<<endl;
    cout<<"!__STL_ASSERTIONS is ending.............."<<endl;
#endif


}
*/
////////////////////////////////////////////////////////////////////////
/*
template <typename T>
class teststatictmpclass
{
public:
    static long _data;
};

template<> long teststatictmpclass<int>::_data = 1;
template<> long teststatictmpclass<char>::_data = 2;
void teststaticmemberintemplate()
{
    cout<<"teststatictmpclass<int>::_data = "<<teststatictmpclass<int>::_data<<endl;
    cout<<"teststatictmpclass<char>::_data = "<<teststatictmpclass<char>::_data<<endl;


    teststatictmpclass<int> objint1,objint2;
    teststatictmpclass<char> objchar1,objchar2;

    cout<<"objint1._data = "<<objint1._data<<endl;
    cout<<"objint2._data = "<<objint2._data<<endl;

    cout<<"objchar1._data = "<<objchar1._data<<endl;
    cout<<"objchar2._data = "<<objchar2._data<<endl;

    objint1._data = 3;
    objchar2._data = 4;
    cout<<"objint1._data = "<<objint1._data<<endl;
    cout<<"objint2._data = "<<objint2._data<<endl;

    cout<<"objchar1._data = "<<objchar1._data<<endl;
    cout<<"objchar2._data = "<<objchar2._data<<endl;


}
*/
//////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/*
template<class I, class O>
struct testPartiClass{
    testPartiClass()
    {
        cout<<"I,O.."<<endl;
    }
};

template<class T>
struct testPartiClass<T*,T*>
{
    testPartiClass()
    {
        cout<<"T*,T*"<<endl;
    }
};

template<class T>
struct testPartiClass<const T*,T*>
{
    testPartiClass()
    {
        cout<<"const T*,T*"<<endl;
    }
};

template<class T>
struct testPartiClass<const T*,const T*>
{
    testPartiClass()
    {
        cout<<"const T*,const T*"<<endl;
    }
};

void testPairiclass()
{
    testPartiClass<int,char> obj1;
    testPartiClass<int*,int*> obj2;
    testPartiClass<const int*,int*> obj3;
    testPartiClass<const int*,const int*> obj4;
}
*/
////////////////////////////////////////////////////////////////////////
// __STL_FUNCTION_TMPL_PARTIAL_ORDER
////////////////////////////////////////////////////////////////////////
/*
class alloc{
};

template<class T,class Alloc = alloc>
class vector{
public:
    void swap(vector<T,Alloc> &)
    {
        cout<<"swap()"<<endl;
    }
    //class template 之内是否可再有temlate mbmbers
public:
    typedef T value_type;
    typedef value_type* iterator;

    template <class I>
    void insert(iterator position,I first, I last)
    {
        cout<<"INSERT()" <<endl;
    }
};
//define global swap function not called the standered function
template <class T,class Alloc>
inline void swap(vector<T,Alloc> &x,vector<T,Alloc> &y)
{
    x.swap(y);
}


void testSTLfunctiontmplparitialorder()
{
    vector<int> x,y;

    swap(x,y);
}


void testclasstemplateistemplatehave()
{
    int ia[5] = {0,1,2,3,4};
    vector<int> x;
    vector<int>::iterator ite = NULL;
    x.insert(ite,ia,ia+4);

}
*/
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/*
template<class T,class Alloc = alloc,size_t BufSiz = 0>
class deque
{
public:
    deque()
    {
        cout<<"deque()"<<endl;
    }
};

//STL_LIMITED_DEFAULT_TEMPLATES
template<class T, class Sequence = deque<T> >
class stack
{
public:
 stack()
 {
    cout<<"stack"<<endl;
 }
private:
 Sequence c;
};

void testdefaulttemplates()
{
    stack<int> x;
}*/
// STL_NON_TYPE_TMP_PARAM_BUG
//////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/*
inline size_t __deque_buf_size(size_t n,size_t sz)
{
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator{
    typedef __deque_iterator<T,T&,T*,BufSiz> iterator;
    typedef __deque_iterator<T,const T&,const T*, BufSiz> const_iterator;

    static size_t buf_size()
    {
        return __deque_buf_size(BufSiz,sizeof(T));
    }
};

//非类型模板参数：size_t BufSiz 就是非类型模板参数，可以用来传递常量（如缓冲区大小）。
template <class T,class Alloc = alloc, size_t BufSiz = 0>
class deque{
public:
    typedef __deque_iterator<T,T&,T*,BufSiz> iterator;

};

void testnotypetamplate()
{
    cout<<deque<int>::iterator::buf_size()<<endl;
    cout<<deque<int,alloc,64>::iterator::buf_size()<<endl;
}
*/
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
/*
class alloc{

};

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque{
public:
    deque()
    {
        cout<<"deque()..."<<endl;
    }
};

template <class T, class Sequence>
class stack;


template <class T, class Sequence>
bool operator==(const stack<T,Sequence> &x,const stack<T,Sequence> &y);

template< class T, class Sequence>
bool operator< (const stack<T,Sequence> &x,const stack<T,Sequence> &y);


template <class T, class Sequence = deque<T> >
class stack{
    friend bool operator== <T> (const stack<T> &,const stack<T> &);
    friend bool operator< <T> (const stack<T> &,const stack<T> &);

    //or
    friend bool operator== <T> (const stack &,const stack &);
    friend bool operator< <T> (const stack &,const stack &);

    //or
    friend bool operator== <> (const stack &,const stack &);
    friend bool operator<  <> (const stack &,const stack &);


    //forbid
    // friend bool operator==  (const stack &,const stack &);
    // friend bool operator< (const stack &,const stack &);
public:
    stack()
    {
        cout<<"stack() "<<endl;
    }
private:
    Sequence c;

};


template <class T, class Sequence >
bool operator== (const stack<T,Sequence> &x,const stack<T,Sequence> &y)
{
    cout << "operator==" << '\t';
    return true;
}


template <class T, class Sequence >
bool operator< (const stack<T,Sequence> &x,const stack<T,Sequence> &y )
{
    cout << "operator<" << '\t';
    return true;
}

void teststlnulltempargs()
{
    stack<int> x;
    stack<int> y;

    cout<<(x == y )<<endl;
    cout<<(x < y )<<endl;


    stack<char> y1;

}
*/
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
// void testspacialization()
// {
//     xmspace::hash<long> t1;
//     xmspace::hash<char> t2;
//     xmspace::hash<unsigned char> t3;
//     t1();
//     t2();
//     t3();
// }

/*
int main()
{
    // testconfigofcompiler();
    // teststaticmemberintemplate();
    // testPairiclass();
    // testSTLfunctiontmplparitialorder();
    // testclasstemplateistemplatehave();
    // testdefaulttemplates();
    // testnotypetamplate();
    // teststlnulltempargs();
    testspacialization();
    return 0;
}*/